/**
 * 选择排序
 * 1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
 * 2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
 * 3. 重复第二步，直到所有元素均排序完毕
 * 对于长度为N的数组，选择排序需要大约N^2/2次比较和N次交换。
 * 有两个特点：①运行时间和输入无关 ②数据移动是最少的，交换次数和数组的大小是线性关系
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  // 循环不变量：[0, i) 有序，且该区间里所有元素就是最终排定的样子
  // 选择区间 [i, len - 1] 里最小的元素的索引，交换到下标 i
  for (let i = 0; i < nums.length; i++) {
    // 记录最小索引
    let min = i;
    // 遍历找到 nums[i+1, ... ,N] 中的最小元索引
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[min]) {
        min = j;
      }
    }
    // 将nums[i] 与 nums[i+1, ... ,N]中最小的元素交换
    let temp = nums[min];
    nums[min] = nums[i];
    nums[i] = temp;
  }
  return nums;
};
